package net.cyndeline.scalarlib.rldungeon.dgs.strategy.pointlessArea.help

import net.cyndeline.scalarlib.rldungeon.dgs.strategy.help.CollapsedNode
import net.cyndeline.scalarlib.rldungeon.dgs.graph.Room

/**
 * Dependency injection.
 */
trait EdgesBelowNodes[VType <: Room[VType]] {
  def edgeAmountBelow(parent: NodeStorage[CollapsedNode[VType]]): Int
  def edgesBelow(parent: NodeStorage[CollapsedNode[VType]]): Set[(NodeStorage[CollapsedNode[VType]], NodeStorage[CollapsedNode[VType]])]
  def registerEdges(parent: NodeStorage[CollapsedNode[VType]], edges: Set[(NodeStorage[CollapsedNode[VType]], NodeStorage[CollapsedNode[VType]])])
  def removeEdges(edges: Set[(NodeStorage[CollapsedNode[VType]], NodeStorage[CollapsedNode[VType]])])
}

/**
 * Keeps track of the set of meaningful edges that exists below a node along the main path in a graph.
 *
 * @constructor Create a new edge map based on a main path.
 * @param mainPath The path from start to goal in a graph level. The first element is the start node, the
 *                 last element is the goal. No node should occur more than once (i.e no cycles).
 */
class EdgesBelowNodesMapping[VType <: Room[VType]](mainPath: Vector[NodeStorage[CollapsedNode[VType]]]) extends EdgesBelowNodes[VType] {
  if (mainPath.size < 1)
    throw new IllegalArgumentException("The level must contain a main path to compute pointless areas, currently empty.")

  private var storageMapping = Map[NodeStorage[CollapsedNode[VType]], LinkedStorage]()
  private val lastStorage = setup() // Add parent entries.

  /**
   * Checks how many meaningful edges still eligible for responders exist below a node on the main path.
   * Takes constant time.
   *
   * @param parent Node on the main path.
   * @return The number of meaningful edges below the node that can hold responders, or throws an exception if
   *         the specified node does not exist on the path.
   */
  override def edgeAmountBelow(parent: NodeStorage[CollapsedNode[VType]]): Int = getParent(parent).edgeAmount

  /**
   * Checks which edges exist below a parent node along the main path. Takes constant time.
   * @param parent Parent to find edges below.
   * @return The set of all edges below a parent (closer to the goal).
   */
  override def edgesBelow(parent: NodeStorage[CollapsedNode[VType]]): Set[(NodeStorage[CollapsedNode[VType]], NodeStorage[CollapsedNode[VType]])] = {
    getParent(parent).edgesBelowThisNode
  }

  /**
   * Adds an edge as belonging to a parent on the main path (i.e the edge can be reached from the parent without
   * traversing another edge on the main path). Calling this method adds the edge to the parent, and also updates every
   * other parent entry above the parent (further away from the goal) by adding the new edge set to the parent
   * entries in O(n) time.
   *
   * When adding an edge along the main path, it should be added to the node closer to the goal, in order for it to
   * be registered as "below" the node above it. Example: Given the path A -> B -> C -> D, the edge B -> C should be
   * registered at C in order to appear below B. Similarly, C -> D should be registered at D.
   *
   * @param parent Parent of edge on the main path.
   * @param edges Edges to register. Element ordering each tuple matter.
   */
  override def registerEdges(parent: NodeStorage[CollapsedNode[VType]], edges: Set[(NodeStorage[CollapsedNode[VType]], NodeStorage[CollapsedNode[VType]])]) {
    if (edges.isEmpty) return

    val parentNode: LinkedStorage = getParent(parent)
    var currentParent = parentNode

    while (currentParent.hasPrevious) {
      currentParent = currentParent.previous
      currentParent.edgesBelowThisNode = currentParent.edgesBelowThisNode union edges
    }
  }

  /**
   * De-associates a set of edges with a parent, ensuring that those edges no longer appear as "below" for the
   * parents above the specified parent. Takes O(n) time.
   * @param edges Edges to remove.
   */
  override def removeEdges(edges: Set[(NodeStorage[CollapsedNode[VType]], NodeStorage[CollapsedNode[VType]])]) {
    if (edges.isEmpty) return

    var currentParent = lastStorage

    while (currentParent.hasPrevious) {
      currentParent = currentParent.previous
      currentParent.edgesBelowThisNode = currentParent.edgesBelowThisNode diff edges
    }
  }

  override def toString: String = {
    var str = ""

    for (m <- storageMapping.keys) {
      str += "Edges below " + m.node + ":\n"
      str += edgesBelow(m).map(tuple => (tuple._1.node, tuple._2.node)).mkString(", ") + "\n"
    }

    str
  }

  /**
   * Sets up every parents entry and next/previous links, along with an empty edge set.
   */
  private def setup(): LinkedStorage = {
    val pathFromGoalToStart = mainPath.reverse.iterator

    var currentNode = pathFromGoalToStart.next() // Path is guaranteed to have at least two entries.
    var currentStorage: LinkedStorage = new LinkedStorage(currentNode)
    storageMapping += (currentNode -> currentStorage)
    val lastStorage = currentStorage

    while (pathFromGoalToStart.hasNext) {
      val newNode = pathFromGoalToStart.next()
      val newStorage = new LinkedStorage(newNode)

      newStorage.next = currentStorage
      storageMapping += (newNode -> newStorage)

      currentStorage.previous = newStorage

      currentNode = newNode
      currentStorage = newStorage
    }

    lastStorage
  }

  private def getParent(parent: NodeStorage[CollapsedNode[VType]]): LinkedStorage = {
    storageMapping.getOrElse(parent, throw new IllegalArgumentException("No parent matching " + parent + " found amongst parents: " + storageMapping.keys.mkString(",")))
  }

  private class LinkedStorage(val storage: NodeStorage[CollapsedNode[VType]]) {
    var previous: LinkedStorage = null
    var next: LinkedStorage = null
    var edgesBelowThisNode = Set[(NodeStorage[CollapsedNode[VType]], NodeStorage[CollapsedNode[VType]])]()

    def hasNext: Boolean = next != null
    def hasPrevious: Boolean = previous != null
    def edgeAmount = edgesBelowThisNode.size
  }

}
